<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            时间：O(n * m * l) m是每次递归遍历字典的长度，n是s的长度，l是单词的平均长度，最坏情况是从s的0-n都要递归一次，因为有记忆化搜索，所以每个索引只用递归一次；否则就是指数级别；m ^ n，每次都会遍历所有的字典，无数个m相乘
            空间：O(n + m * l)。n-递归站，m * l就是m个单词，每个单词的平均长度是l
        */

        var wordBreak = function(s, wordDict) {
            // 1. 写初始化
            // 2. 写递归函数
            // 3. 写比较函数
            let memo = {}
            let set = new Set(wordDict) // 为什么用set，为了去除重复的测试用例
            function backtrack (start) {
                // 成功退出条件
                if (start === s.length) return true
                // 剪枝
                if (start in memo) return memo[start]
                debugger
                for (const word of set) {
                    debugger
                    // 从'' 拼接上来leet，看leet是否和'leetcode'的前面部分是匹配的
                    if (isMatch(s, start, word)) {
                        if (backtrack(start + word.length)) {
                            // 意味着从start到字符串末尾可以拆分
                            memo[start] = true
                            return true
                        }
                    }
                }

                // 意味着从start到字符串末尾不能拆分
                memo[start] = false
                return false
            }

            function isMatch(s, start, word) {
                // 如果长度超出，return
                if (start + word.length > s.length) return false
                // 每个字符都要比较
                for (let i = 0; i < word.length; i++) {
                    if (s[start + i] !== word[i]) return false
                }
                return true
            }

            return backtrack(0)
        };
        // console.log(wordBreak("leetcode", ["leet", "code"]));
        // console.log(wordBreak("catsandog", ["cats", "dog", "sand",  "and", "o", "cat"]));
        // console.log(wordBreak("catsandog", ["cats", "dog", "an", "sand", "and", "cat"]));
        console.log(wordBreak("applepenapple", ["apple", "pen"]));
        // // 超出时间限制
        // console.log(wordBreak("bccdbacdbdacddabbaaaadababadad", ["cbc","bcda","adb","ddca","bad","bbb","dad","dac","ba","aa","bd","abab","bb","dbda","cb","caccc","d","dd","aadb","cc","b","bcc","bcd","cd","cbca","bbd","ddd","dabb","ab","acd","a","bbcc","cdcbd","cada","dbca","ac","abacd","cba","cdb","dbac","aada","cdcda","cdc","dbc","dbcb","bdb","ddbdd","cadaa","ddbc","babb"]));
    </script>
</body>

</html>